﻿
namespace SortAndDatastruct {
    /// <summary>
    /// 基数排序算法，内部数位排序使用计数排序实现[需要额外空间]
    /// 排序接口，没有设置最高位参数，而在内部实现中加入了遍历查找最高位的算法
    /// </summary>
    class RadixSort :ISort {
        /// <summary>
        /// 返回该数字的有几位
        /// </summary>
        /// <param name="Num">一个整数</param>
        /// <returns>位数</returns>
        int BitCnt (int Num) {
            int cnt = 0;
            while (true) {
                Num /= 10;
                ++cnt;
                if (Num == 0) break;
            }
            return cnt;
        }
        /// <summary>
        /// 获取整数指定位置的数字，1表示最低位
        /// </summary>
        /// <param name="Num">整数</param>
        /// <param name="Position">数位</param>
        /// <returns>指定位置的数字</returns>
        int GetDigital (int Num,int Position) {
            if (Position < 1) return 0;
            while (Position != 1) {
                Num /= 10;
                Position -= 1;
            }
            return Num % 10;
        }
        /// <summary>
        /// 排序接口
        /// </summary>
        /// <param name="Array">带排序数组</param>
        internal override void Sort (ref int[] Array) {
            if (Array == null || Array.Length < 2) return;
            int highest = 0;
            //遍历数字，得知最高有几位数。
            //实际算法中，应该在参数中设置。
            foreach (var item in Array) {
                int bit = BitCnt(item);
                if (highest < bit) highest = bit;
            }
            if (highest == 0) return;
            int[] ResultArr = new int[Array.Length];
            //使用计数排序-稳定的排序来进行数位排序
            for (int i = 1; i <= highest; ++i) {
                int[] cntArr = new int[10];//每个数位需要比较的，从0-9 这十个数
                for (int j = 0; j < Array.Length; ++j) {
                    int digital = GetDigital(Array[j],i);
                    cntArr[digital] += 1;
                }
                for (int k = 1; k < cntArr.Length; ++k) {
                    cntArr[k] += cntArr[k - 1];
                }
                for (int p = Array.Length - 1; p >= 0; p--) {
                    int digit = GetDigital(Array[p],i);
                    ResultArr[cntArr[digit] - 1] = Array[p];
                    cntArr[digit] -= 1;
                }
                //下一个数位的排序将使用这一次排序的结果
                //resulteArr.CopyTo((System.Array)Array,0);
                for (int j = 0; j < Array.Length; ++j) {
                    Array[j] = ResultArr[j];
                }
            }
            
        }
    }
}
